from linear_algebra import normalize, norm, Vector, scalar_prod
import copy
import random

# from nicolas hoening
def biasedChoice(n):
    ''' Choose a random index from a range
        first elements are chosen more frequently than later ones.
        Weigths are linearly assigned, given n elements, the first
        has weight n, second n-1, ..., the last has weight 1
    '''
    sumw = ((n+1) * n) // 2
    x = random.randint(1, sumw)
    F = 0
    for i in xrange(1, n+1):
        F += i # steps are getting bigger (-> probabilities for x lying in them)
        if x <= F: return n-i
    return 0 # we should not reach this


# This can also be set to a different value in the problem-specification
generateIndex = biasedChoice
# If an entry's value is larger than cutoff
CUTOFF_FACTOR = 2


class Population(list):
    """ A list of entries/vectors, from which one can select."""

    def __new__(cls, *args):
        return list.__new__(cls)

    def __init__(self, contents = None):
        list.__init__(self)
        if contents:
            self.extend(contents)
        self.min_size = len(self) + 1
        self.size_aggreg = len(self)
        self.average = 0
        self.max_size = max_size


    def select(self):
        """Selects an element from population to given specimen."""
        i = generateIndex(len(self))
        if isinstance(self[i], SpecialEntry):
            return self[i].getEntry()
        else:
            return self[i]


    def add(self, entry, value):
        """Newly adds and instates a previously not contained entry to population."""
        entry.value = 0
        entry.tries = 0
        index = 0

        if hasattr(entry, "parent"):
            index = self.index(entry.parent)
            self.valuate(entry.parent, value, factor = 0.75)
            del entry.parent
        else:
            index = len(self) / 2

        n = len(self)
        self.average *= n/(n+1) # adjust denominator of average
        self.insert(index, entry)
        self.valuate(entry, value)


        self.size_aggreg += len(self)

        if self.size_aggreg > self.max_size:
            population.size_aggreg -= self.max_size
                population.kill(pop[-1])


    def valuate(self, entry, value, factor = 1):
        """Assigns a value to an already added entry.

           Also updates relevant averages."""

        n = len(self)

        self.average -= entry.value/n
        entry.value += factor * value
        entry.value *= 1/(1+factor)
        self.average += entry.value/n

        self.update(entry)


    def update(self, entry):
        """Moves an entry to its correct position in self.

           Assumes that all other entries are in correct order. Not threadsafe!
           Also weeds out outdated entries."""

        index = self.index(entry)
        n = len(self)
        i = index - 1
        while i and entry.value < self[i].value:
            i -= 1

        i += 1

        if i == index:
            i += 1
            while i < n and entry.value > self[i].value:
                i += 1

            i -= 1

        self.remove(entry)
        self.insert(i, entry)

        if self[-1].value > self[0].value + CUTOFF_FACTOR * (self.average - self[0].value):
            del_index = biasedChoice(len(self) - 1) + 1
            if not isinstance(self[0 - index], SpecialEntry):
                self.kill(self[0 - index])


    def kill(self, entry):
        if len(self) > self.min_size:
            self.remove(entry)
            n = len(self)

            self.average *= (n+1)/n
            self.average -= entry.value/n

    def findMate(self, entry):
        """Called by mating entry.

           Only returns select() for this type of population."""
        return self.select()
